package algorithm.exhaustion;

import java.util.ArrayDeque;
import java.util.Iterator;

/**
 * 有三个容积分别是3升、5升和8升的水桶，其中容积为8升的水桶中装满了水，容积为3升和容积为5升的水桶是空的。
 * 三个水桶都没有体积刻度，现在需要将大水桶中的8升水等分成两份，每份都是4升水，附加条件是只能使用另外两个空水桶，不能借助其他辅助容器。
 * @author xuyuji
 *
 */
public class Ae2 {
	
	private int i = 1;
	
	private ArrayDeque<BucketState> states = new ArrayDeque<BucketState>();
	
	public static void main(String[] args) {
		new Ae2().execute();
	}
	
	public void execute(){
		states.add(new BucketState(new int[]{8, 0, 0}, null));
		searchState();
	}
	
	private void searchState(){
		BucketState current = states.peekLast();
		if(current.isFinish()){
			printStates();
			return;
		}else{
			for(int i = 0; i < 3; i++){
				for(int j = 0; j < 3; j++){
					searchStateOnAction(current, i, j);
				}
			}
		}
	}
	
	private void searchStateOnAction(BucketState current, int from, int to){
		if(current.canTakeDumpAction(from, to)){
			BucketState next = new BucketState();
			current.DumpWater(from, to, next);
			if(!IsProcessedState(next)){
				states.add(next);
				searchState();
				states.pollLast();
			}
		}
	}
	
	private void printStates(){
		System.out.println(String.format("##方法%d##", i));
		for(BucketState bs : states){
			System.out.println(bs);
		}
		System.out.println(String.format("##方法%d##\n", i++));
	}
	
	private boolean IsProcessedState(BucketState next){
		Iterator<BucketState> it = states.iterator();
		while(it.hasNext()){
			BucketState bs = it.next();
			if(next.isSameState(bs)){
				return true;
			}
		}
		return false;
	}
}

class TagAction{
	int from;
	int to;
	int water;
	
	public TagAction(int from, int to, int water) {
		this.from = from;
		this.to = to;
		this.water = water;
	}

	public int getFrom() {
		return from;
	}

	public void setFrom(int from) {
		this.from = from;
	}

	public int getTo() {
		return to;
	}

	public void setTo(int to) {
		this.to = to;
	}

	public int getWater() {
		return water;
	}

	public void setWater(int water) {
		this.water = water;
	}
	
	@Override
	public String toString() {
		String[] dumpWater = new String[]{" 0", " 0", " 0"};
		dumpWater[from] = "-" + water;
		dumpWater[to] = "+" + water;
		
		StringBuilder sb = new StringBuilder();
		sb.append("{");
		sb.append(dumpWater[0]).append(",").append(dumpWater[1]).append(",").append(dumpWater[2]);
		sb.append("}");
		return sb.toString();
	}
}

class BucketState{
	private static int[] bucket_capacity = new int[]{8, 5, 3};
	private int[] bucket_s;	//依次表示8升桶水量、5升桶水量、3升桶水量，长度必须是3，简单demo，这里就不校验了
	private TagAction curAction;
	
	public BucketState() {
	}
	
	public BucketState(int[] bs, TagAction action) {
		this.bucket_s = bs;
		this.curAction = action;
	}
	
	public boolean isFinish(){
		if(bucket_s[0] == 4 && bucket_s[1] == 4){
			return true;
		}else{
			return false;
		}
	}
	
	public boolean canTakeDumpAction(int from, int to){
		if(from != to && !IsBucketEmpty(from) && !IsBucketFull(to)){
			return true;
		}else{
			return false;
		}
	}
	
	private boolean IsBucketEmpty(int bucketNo){
		if(bucket_s[bucketNo] == 0){
			return true;
		}else{
			return false;
		}
	}
	
	private boolean IsBucketFull(int bucketNo){
		if(bucket_s[bucketNo] == bucket_capacity[bucketNo]){
			return true;
		}else{
			return false;
		}
	}
	
	public void DumpWater(int from, int to, BucketState next){
		int[] next_bucket_s = new int[]{bucket_s[0], bucket_s[1], bucket_s[2]};
		
		int from_w = bucket_s[from];
		int to_w = bucket_s[to];
		int to_c = bucket_capacity[to];
		int dumpWater = to_c - to_w > from_w ? from_w : to_c - to_w;
		
		next_bucket_s[from] -= dumpWater;
		next_bucket_s[to] += dumpWater;
		
		next.setBucket_s(next_bucket_s);
		next.setCurAction(new TagAction(from, to, dumpWater));
	}
	
	public int[] getBucket_s() {
		return bucket_s;
	}

	public void setBucket_s(int[] bucket_s) {
		this.bucket_s = bucket_s;
	}

	public TagAction getCurAction() {
		return curAction;
	}

	public void setCurAction(TagAction curAction) {
		this.curAction = curAction;
	}

	public boolean isSameState(BucketState bs){
		int[] bucket_s_ = bs.getBucket_s();
		if(bucket_s[0] == bucket_s_[0]
				&& bucket_s[1] == bucket_s_[1]
				&& bucket_s[2] == bucket_s_[2]){
			return true;
		}else{
			return false;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if(curAction != null){
			sb.append(curAction);
			sb.append(" => ");
		}
		sb.append("[");
		sb.append(bucket_s[0]).append(",");
		sb.append(bucket_s[1]).append(",");
		sb.append(bucket_s[2]);
		sb.append("]");
		return sb.toString();
	}
}
